/*    Copyright 2010 Tobias Marschall
 *
 *    This file is part of MoSDi.
 *
 *    MoSDi is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    MoSDi is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with MoSDi.  If not, see <http://www.gnu.org/licenses/>.
 */

package mosdi.fa;

import java.util.ArrayList;
import java.util.List;

import mosdi.util.BitArray;

/** NFA recognizing instances of a set of generalized strings including a 
 *  Edit neighborhood (i.e. all strings with an edit distance <= allowedDistance
 *  are reported as a match). */
public class GeneralizedStringsEditNFA extends NFA {

	private int allowedDistance;
	/** A NFA recognizing the given generalized strings (without Edit 
	 *  neighborhood). */
	private GeneralizedStringsNFA nfa; 
	
	public GeneralizedStringsEditNFA(List<GeneralizedString> strings, int allowedDistance) {
		this.allowedDistance = allowedDistance;
		this.nfa = new GeneralizedStringsNFA(strings);
	}
	
	/** Given a separate BitArray for each error count, assembles a
	 *  joint BitArray containing all states. */
	private BitArray assembleStateSet(List<BitArray> stateSets) {
		return BitArray.join(stateSets);
	}
	
	/** Counterpart to assembleStateSet(). */
	private List<BitArray> dissembleStateSet(BitArray stateSet) {
		List<BitArray> list = new ArrayList<BitArray>(allowedDistance+1);
		for (int i=0; i<=allowedDistance; ++i) {
			list.add(stateSet.copyOfSubarray(i*nfa.stateCount(), (i+1)*nfa.stateCount()));
		}
		return list;
	}
	
	/** Assembles a state set for all error counts by duplicating the state set 
	 *  for the single NFA. */
	private BitArray multiplyStateSet(BitArray stateSet) {
		List<BitArray> list = new ArrayList<BitArray>(allowedDistance+1);
		for (int i=0; i<=allowedDistance; ++i) list.add(stateSet);
		return assembleStateSet(list);
	}
	
	@Override
	public BitArray acceptStates() {
		return multiplyStateSet(nfa.acceptStates());
	}

	@Override
	public int alphabetSize() {
		return nfa.alphabetSize();
	}

	@Override
	public BitArray startStates() {
		return multiplyStateSet(nfa.startStates());
	}

	@Override
	public int stateCount() {
		return (allowedDistance+1) * nfa.stateCount();
	}

	@Override
	public BitArray transition(BitArray activeStates, int character) {
		List<BitArray> stateSets = dissembleStateSet(activeStates);
		List<BitArray> newStateSets = new ArrayList<BitArray>(allowedDistance+1);
		// states to be ORed to the states for k+1
		BitArray carryStates = null;
		for (int k=0; k<=allowedDistance; ++k) {
			BitArray b = nfa.transition(stateSets.get(k), character);
			if (carryStates!=null) b.or(carryStates);
			newStateSets.add(b);
			carryStates = nfa.readWildcard(stateSets.get(k)); // substitutions
			carryStates.or(nfa.readWildcard(b)); // substitutions
			carryStates.or(stateSets.get(k)); // insertions
		}
		return assembleStateSet(newStateSets);
	}

	@Override
	public int matchCount(BitArray states) {
		List<BitArray> stateSets = dissembleStateSet(states);
		BitArray b = new BitArray(nfa.stateCount());
		for (BitArray stateSet : stateSets) b.or(stateSet);
		b.and(nfa.acceptStates());
		return b.numberOfOnes();
	}	

}
